// https://leetcode.cn/problems/maximum-width-of-binary-tree/

// 题干：给你一棵二叉树的根节点 root ，返回树的 最大宽度 。
//      树的 最大宽度 是所有层中最大的 宽度 。
//      每一层的 宽度 被定义为该层最左和最右的非空节点（即，两个端点）之间的长度。
//      将这个二叉树视作与满二叉树结构相同，两端点间会出现一些延伸到这一层的 null 节点，这些 null 节点也计入长度。
//      题目数据保证答案将会在  32 位 带符号整数范围内

// 示例：输入：root = [1,3,2,5,null,null,9,6,null,7]
//      输出：7

// 碎语：记住空结点也算在内
//       考虑利用数组存储二叉树的方式，给结点编号

#include <bits/stdc++.h>
using namespace std;

struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode() : val(0), left(nullptr), right(nullptr) {}
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
    TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};

class Solution
{
public:
    void deleteTree(TreeNode* root) {
        if (root == nullptr) {
            return;
        }

        deleteTree(root->left);
        deleteTree(root->right);

        delete root;
    }

    int widthOfBinaryTree(TreeNode* root)
    {
        vector<pair<TreeNode*, unsigned int>> q; // 用数组模拟队列
        q.push_back({root, 1});
        unsigned int ret = 0;

        while (q.size()) { // 处理当前层
            // 先更新这一层
            auto &[x1, y1] = q[0];
            auto &[x2, y2] = q.back();
            ret = max(ret, y2 - y1 + 1);

            // 让下一层入队
            vector<pair<TreeNode *, unsigned int>> tmp; // 让下一层进入这个队列，直接开个新数组替换
            for (auto &[x, y]: q) {
                if (x->left) tmp.push_back({x->left, y * 2});
                if (x->right) tmp.push_back({x->right, y * 2 + 1});
            }
            q = tmp;
        }

        return ret;
    }
};

int main()
{
    Solution sol;

    auto root = new TreeNode(1);
    root->left = new TreeNode(3);
    root->right = new TreeNode(2);
    root->left->left = new TreeNode(5);
    root->left->right = new TreeNode(3);
    root->right->right = new TreeNode(9);

    cout << sol.widthOfBinaryTree(root) << endl;
    sol.deleteTree(root);

    return 0;
}








